package com.example.system.class12;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Date 2022/7/30
 * @Author Jonathan
 * @Description 建立二叉树印出来的一些问题
 */
public class CreateBT {
    private static int index = 0;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 8, 12, null, null, null, 4, null, null};
        Queue<Integer> queue = new LinkedList<>(Arrays.asList(arr));
        Node root = createBST2(queue);
        System.out.println("head is:" + root);
        preOrder(root);
        System.out.println("==========================");
        Node root1 = createBST(arr);
        System.out.println("head is:" + root1);
        preOrder(root1);
        System.out.println("==========================");
        final Node root3 = createBST3(arr);
        System.out.println("head is:" + root3);
        preOrder(root3);
    }

    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "value=" + value +
                    ']';
        }
    }

    public static Node createBST(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr, 0);
    }

    public static Node createBST2(Queue<Integer> queue) {
        if (queue == null || queue.size() <= 0) {
            return null;
        }
        return create2(queue);
    }

    public static Node createBST3(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create3(arr);
    }

    // 这个方式不行
    public static Node create(Integer[] arr, Integer index) {
        Integer value = arr[index];
        System.out.printf("index:%d, arr[index]:%d\n", index, arr[index]);
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr, ++index);
        node.right = create(arr, ++index);
        return node;
    }

    // 借助全局变量实现
    public static Node create3(Integer[] arr) {
        Integer value = arr[index++];
        System.out.printf("index:%d, arr[index]:%d\n", index, value);
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create3(arr);
        node.right = create3(arr);
        return node;
    }

    // 借助队列实现
    public static Node create2(Queue<Integer> queue) {
        Integer value = queue.poll();
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create2(queue);
        node.right = create2(queue);
        return node;
    }


    public static void preOrder(Node root) {
        if (root == null) return;
        System.out.println(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }


}
